import java.util.Deque;
import java.util.LinkedList;

public class num1028 {
    /**
     * 先序遍历还原二叉树
     * @param traversal
     * @return
     */
    public TreeNode recoverFromPreorder(String traversal) {
        Deque<TreeNode> stack = new LinkedList<>();//创建一个栈
        char[] chars = traversal.toCharArray();//把字符串变成char数组
        int cur = 0;//标记chars的索引
        while (cur < chars.length){
            //先测深度
            int leve = 0;
            while (chars[cur] == '-'){
                leve++;
                cur++;
            }
            //此时leve就是当前节点的深度值，需要获得节点的值
            int val = 0;
            while (cur < chars.length && Character.isDigit(chars[cur])){
                val = val * 10 + (chars[cur] - '0');
                cur++;
            }
            TreeNode node = new TreeNode(val);
            if(leve == stack.size()){
                if(!stack.isEmpty()){
                    //栈不为空，当前节点是栈顶节点的左孩子
                    stack.peek().left = node;
                }
            }else{
                //深度和栈的size不一样，该节点是栈中当深度和size一样的那个节点的右孩子
                while (leve != stack.size()){
                    stack.pop();
                }
                stack.peek().right = node;
            }
            stack.push(node);
        }
        //此时只需要留下栈中最后一个元素即树根
        while (stack.size() > 1){
            stack.pop();
        }
        return stack.pop();
    }
}
